在開始今天題目之前，先來認識一下凱撒密碼 (Caesar cipher)

凱撒密碼是一種替換加密技術，明文中的所有字母都在字母表上向後按照一個固定數目進行偏移後被替換成密文。例如，當偏移量是3的時候，所有的字母A將被替換成D，B變成E，以此類推。 -wiki

先假設今天input string為 'xyz' → 想要每個字母都shift 2 → 得到 'zab'

直覺的想法可能是：
我們先建立一個陣列來存放我們的input，然後呼叫一個shift的function來對這個陣列的字做位移，最後採用join的方式來得到output string。

那我們來思考這個function的實作：
我們可以使用Unicode(萬國碼)，Unicode給每個字元提供了一個唯一的數位，不論是什麼平臺、不論是什麼程式、不論什麼語言。

如果想要對編碼有更深入的了解，可以參考 瞭解網頁中看不懂的編碼：Unicode 在 JavaScript 中的使用

假設我們有記得：
a 的unicode = 97 (10進位)
z 的unicode = 122
我們要把字母轉換的行為，其實就是把 **舊的字母 + 偏移量 ⇒ 結果 **

但如我我們今天要把z，位移2後想要得到b，我們理所當然的把122 + 2 = 124 ，此時，實際我們會得到別的符號( | )。

所以，我們應該要把124轉換成98，這時候mod(modulo)就派上用場了！
也就是超過122時我們應該回傳 96+ (舊的字母 + 偏移量)％122
⇒ 96 + （122 + 2）%122 = 98 (b)

但如果今天我們遇到偏移量shift = 54，我們把 96 + (122+54) % 122 = 140
發現140仍大於 122 (完蛋？)
所以我們應該要再多做一層檢查我們的(原偏移量 % 26字母數)來當我們的偏移量

把上面的想法轉成程式碼就會像下面

function caesarCipherEncryptor(string, key) {
  const result = [];
	const shift = key % 26;
	for (const letter of string){
		result.push(getResult(letter, shift));
	}
	return result.join('');
}

const getResult = (letter, shift) => {
	const newLetterCode = letter.charCodeAt() + shift;
	return newLetterCode <= 122 ? String.fromCharCode(newLetterCode) : String.fromCharCode(96+ (newLetterCode%122));
}

那如果我們根本忘了unicode，我們可以自己建立一個a~z的陣列
這時候 a = 0, z = 25
這時候公式就會變成 -1 + (字母在陣列中的index + 偏移量)％25

Time : O(n), n 是input string size
Space: O(n)

程式碼如下

function caesarCipherEncryptor(string, key) {
  const result = [];
	const shift = key % 26;
	const AtoZArr = 'abcdefghijklmnopqrstuvwxyz'.split('');
	for (const letter of string){
		result.push(getResult(letter, shift, AtoZArr));
	}
	return result.join('');
}

const getResult = (letter, shift, AtoZArr) => {
	const newLetterCode = AtoZArr.indexOf(letter) + shift;
	return AtoZArr[newLetterCode % 26] ;
}

還沒結束！
別急!讓我們仔細閱讀一下leetcode的題目，它其實就是我們上面的題目改變一下shift的規則

Input: s = "abc", shifts = [3,5,9]

We start with "abc".
After shifting the first 1 letters of s by 3, we have "dbc".
After shifting the first 2 letters of s by 5, we have "igc".
After shifting the first 3 letters of s by 9, we have "rpl", the answer

其實也就是a，總共會被移動3+5+9的位置；b則是移5+9;c則是只移了9
我們只需要額外對shifts做調整即可，相信看完上面的解說應該有想法了吧！
自己都手試試看吧！
我自己的做法就附在最後面～

const getResult = (letter, shift) => {
  const newLetterCode = letter.charCodeAt() + shift;
  return newLetterCode <= 122 ? String.fromCharCode(newLetterCode) : String.fromCharCode(96 + (newLetterCode % 122));
}

var shiftingLetters = function (s, shifts) {
  let result = [];
  const arrOfs = s.split('')
  // 使用prefix sum技巧
  for (let idx = shifts.length - 2; idx >= 0; --idx) {
    shifts[idx] = (shifts[idx] + shifts[idx + 1]);
  }

  for (let i = 0; i < arrOfs.length; i++) {
    result.push(getResult(arrOfs[i], shifts[i] % 26));
  }
  return result.join('')
};

明日題目預告：來點不一樣的資料結構 Remove Duplicates from linked list，一起換一下口味吧。